There has been explosive growth in Internet traffic due to the increased number of Internet users, various service demands from those users, the implementation of new services, such as voice-over-IP (VoIP) or streaming applications, and the development of mobile Internet. Conventional routers, which act as relaying nodes connected to sub-networks or other routers, have accomplished their roles well, in situations in which the time required to process packets, determine their destinations, and forward the packets to the destinations is usually smaller than the transmission time on network paths. More recently, however, the packet transmission capabilities of high-bandwidth network paths and the increases in Internet traffic have combined to outpace the processing capacities of conventional routers.
This has led to the development of massively parallel, distributed architecture routers. A distributed architecture router typically comprises a large number of routing nodes that are coupled to each other via a plurality of switch fabric modules and an optional crossbar switch. Each routing node has its own routing (or forwarding) table for forwarding data packets via other routing nodes to a destination address.
Traditionally, a single processor is used to forward all packets in a router or switch. Even in routers with multiple forwarding table lookup threads, these threads are under control of a single processor and use a single forwarding table. Thus, conventional routers retain route information in a central location and do not distribute route information within the router. Also, since many prior art routers do not have multiple routing nodes, these routers do not experience the problems that arise when a distributed architecture combines routing nodes with small table space with more powerful routing nodes in a large route capacity router.
The main disadvantage of prior art routers is the inability to handle line rate forwarding for high bandwidth links, such as 10 Gbps interfaces. This is especially true for the longest prefix matches encountered when forwarding IPv6 packets. Also, when the table space limitations of current routers are exceeded, the routers drop routes from their routing tables or cease to learn new routes. Thus, conventional routers drop packets that would be routable if adequate table space were available. Conventional routers may use a default route instead of dropping a packet. But there is only one default route for the whole router, so the chances of successfully routing the packet are small. If no default route is defined, conventional routers drop the packets.
Therefore, there is a need in the art for improved high-speed routers. In particular, there is a need for a high-speed router that is not limited in performance by the size requirements of large routing tables in each of a plurality of routing nodes. More particularly, there is a need for a high-speed router that optimizes routing (forwarding) table space by storing routing information in an efficient manner.